package com.wyw.leetcode.learning.simple;

import java.util.Arrays;

/**
 * leetcode topic 350
 * 两个数组的交集
 *      给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
 *      返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。
 *      可以不考虑输出结果的顺序。
 *
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/24 9:20
 */
public class Topic350 {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,2,3};
        int[] nums2 = new int[]{2,2,4};

        int[] intersect = intersect(nums1, nums2);
        for(int i : intersect)
            System.out.print(i + "   ");
    }

    /**
     * 使用哈希表
     * @param nums1
     * @param nums2
     * @return
     */
//    public static int[] intersect(int[] nums1, int[] nums2) {
////        List<Integer> list = new ArrayList();
////        Map<Integer, Integer> map = new HashMap<>();
////        for(int i : nums1) {
////            map.put(i, map.get(i) == null ? 1 : map.get(i) + 1);
////        }
////        for(int i: nums2) {
////            if(map.containsKey(i)) {
////                list.add(i);
////                if(map.get(i)== 1) {
////                    map.remove(i);
////                } else {
////                    map.put(i, map.get(i) - 1);
////                }
////            }
////        }
////        return list.stream().filter(integer -> integer!=null).mapToInt(i->i).toArray();
//
//        if (nums1.length > nums2.length) {
//            return intersect(nums2, nums1);
//        }
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int num : nums1) {
//            int count = map.getOrDefault(num, 0) + 1;
//            map.put(num, count);
//        }
//        int[] intersection = new int[nums1.length];
//        int index = 0;
//        for (int num : nums2) {
//            int count = map.getOrDefault(num, 0);
//            if (count > 0) {
//                intersection[index++] = num;
//                count--;
//                if (count > 0) {
//                    map.put(num, count);
//                } else {
//                    map.remove(num);
//                }
//            }
//        }
//        return Arrays.copyOfRange(intersection, 0, index);
//
//    }

    /**
     * 排序加双指针
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect(int[] nums1, int[] nums2) {

//        int length1 = nums1.length;
//        int length2 = nums2.length;
//        if (length1 > length2) {
//            return intersect(nums2, nums1);
//        }
//
//        Arrays.sort(nums1);
//        Arrays.sort(nums2);
//
//        int[] intersection = new int[length1];
//
//        int i = 0;
//        int j = 0;
//        int index = 0;
//
//        while(i<length1 && j<length2) {
//            if(nums1[i] == nums2[j]) {
//                intersection[index] = nums1[i];
//                i ++;
//                j ++;
//                index ++;
//            } else if (nums1[i] > nums2[j]) {
//                j++;
//            } else {
//                i++;
//            }
//        }
//
//        return Arrays.copyOfRange(intersection, 0, index);

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);

    }

}
